34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6

输出: [-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

思路及算法

在一个有序数组中寻找元素，很容易想到使用「二分查找」

在常见的二分查找题目中只需要寻找一个元素，而这道题需要我们找到「开始元素位置」和「结束元素」

举例：现有一个升序数组 [8, 8, 8] target = 8

当找到索引为1的8时，需要向两边找，分别找到「开始元素」和「结束元素」，所以我们也需要分别写「找开始元素的方法」和「找结束元素的方法」，当然都是使用二分查找法

找「开始元素」

当满足 nums[mid] < target时，说明与target相等值在区间[mid + 1, right]中，所以有 left = mid + 1

否则就是 nums[mid] >= target，因为nums[mid]无法做出判定，即可能是等于target，所以我们保险一点则有 right = mid，下一次查找区间就是 [left, mid]
循环的结束条件是 while left < right，循环结束后还需要判断nums[left]是不是与target相等，不等则返回-1

如果不理解怎么找到「开始元素」，可以举最简单的示例，过一遍就会明白了，例如 [8, 8, 8]，最终会返回 0

代码

def find_first(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) >> 1
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
     if nums[left] != target:
        return -1
     return left

找「结束元素」

当满足nums[mid] > target，说明target是在左边，即下一个搜索区间是[left, mid - 1]，所以有 right = mid - 1
否则就是 nums[mid] <= target，说明 nums[mid] 可能小于 target也可能是等于target，所以为了保险起见，下一个搜索区间是[mid , right]，即left = mid

为了验证和理解，也可以举个简单例子，比如 [8, 8]，此时就会出现死循环，一直满足nums[mid] <= target，要解决这一问题就是 取上界

代码

def find_last(nums, target):
    while left < right:
        # 取上界中间数
        mid = (left + right + 1) >> 1
        if nums[mid] > target:
            right = mid - 1
        else:
            left = mid
     if nums[left] != target:
		return -1
     return left

完整代码

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        size = len(nums)
        if size == 0:
            return [-1, -1]
            
        first = self.find_first(nums, target)
        if first == -1:
            return[-1, -1]
        last = self.find_last(nums, target)
        return [first, last]


    def find_first(self, nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        if nums[left] != target:
            return -1
        return left

    def find_last(nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            # 取上界中间数
            mid = (left + right + 1) >> 1
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid

        # 在find_first()执行时，判断过了，如果不存在就已经直接返回了
        # 能执行到这里，说明此数组必定存在target等值元素，所以一定会找到
        # if nums[left] != target:
        #     return -1
        return left